package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
 *
 * <p>返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * <p>}
 */
public class Test863 {
    Map<Integer,TreeNode3> map = new HashMap<>();

    List<Integer> list = new ArrayList<>();
    public List<Integer> distanceK(TreeNode3 root, TreeNode3 target, int k) {
        findParent(root);
        findAnswer(target,null,0,k);
        return list;
    }

    public void findParent(TreeNode3 node){
        if(node.left !=null){
            map.put(node.left.val,node);
            findParent(node.left);
        }
        if (node.right != null){
            map.put(node.right.val,node);
            findParent(node.right);
        }
    }

    public void findAnswer(TreeNode3 target,TreeNode3 from,int depth,int k){
        if(target == null){
            return;
        }
        if (depth == k) {
            list.add(target.val);
            return;
        }
        if (target.left != from) {
            findAnswer(target.left, target, depth + 1, k);
        }
        if (target.right != from) {
            findAnswer(target.right, target, depth + 1, k);
        }
        if (map.get(target.val) != from) {
            findAnswer(map.get(target.val), target, depth + 1, k);
        }


    }
}


class TreeNode3 {
      int val;
      TreeNode3 left;
      TreeNode3 right;
      TreeNode3(int x) { val = x; }
  }